
#include"hashutil.h"
#include"singletable.h"
#include<iostream>
#include<ctime>
enum Status {
  OK = 0,
  NotFound = 1,
  NotEnoughSpace = 2,
  NotSupported = 3,
};

const uint32_t kMaxCuckooCount = 500;

template<typename ItemType, uint32_t bitsPerItem,
	template<uint32_t> class TableType=SingleTable,
	typename HashFamily=cuckoofilter::TwoIndependentMultiplyShift>
class CuckooFilter {
 private:
  // 存储每一个项目
  TableType<bitsPerItem> *table_;
  uint32_t numItems_;
  struct VictimCache {
	uint32_t index;
	uint32_t tag;
	bool used;
  };

  // 保存最终没有找到最终位置的元素
  VictimCache victim_;
  // 哈希集合
  HashFamily hasher_;

  // 返回到对应Bucket 的索引
  uint32_t IndexHash(uint32_t hv) const {
	return hv & (table_->NumBuckets() - 1);
  }

  // 返回 Tag 的索引
  uint32_t TagHash(uint32_t hv) const {
	uint32_t tag;
	tag = hv & ((1ULL << bitsPerItem) - 1);
	tag += (tag == 0);
	return tag;
  }

  // 对获取 Bucket 和 Tag 的索引做了一层封装
  void GenerateIndexTagHash(const ItemType &item, uint32_t &index, uint32_t &tag) const {
	const uint64_t hash = hasher_(item);
	index = IndexHash(hash >> 32);
	tag = TagHash(hash);
  }

  uint32_t AltIndex(const uint32_t index, const uint32_t tag) const {
	return IndexHash(static_cast<uint32_t>(index ^ (tag * 0x5bd1e995)));
  }
  // 添加元素的实现，提供给上层 Add() 调用
  Status AddImpl(uint32_t i, const uint32_t tag);

  // 加载负载因子
  double LoadFactor() const {
	return 1.0 * Size() / table_->SizeInTags();
  }

  // 每一个Item 占用的内存
  double BitsPerItem() const {
	return 8.0 * table_->SizeInBytes() / Size();
  }

 public:
  // 构造函数
  explicit CuckooFilter(const uint32_t maxNumKeys) : numItems_(0), victim_(), hasher_() {
	std::clock_t start;
	uint32_t assoc = 4;
	uint32_t numBuckets = upperPower2(std::max<uint64_t>(1, maxNumKeys / assoc));
	double frac = (double)maxNumKeys / numBuckets / assoc;


	if (frac > 0.96) {
	  numBuckets <<= 1;
	}

	victim_.used = false;
	table_ = new TableType<bitsPerItem>(numBuckets);

  }

  // 析构函数

  ~CuckooFilter() {
	delete table_;
  }

  //添加一个元素到过滤器
  Status Add(const ItemType &item);

  //查询某一个元素是否存在于过滤器中
  Status Contain(const ItemType &key) const;

  // 删除一个key从过滤器中
  Status Delete(const ItemType &key);

  // 提供状态信息
  std::string Info() const;

  // 返回已经插入的元素的数量
  uint32_t Size() const {
	return numItems_;
  }

  // 返回整个过滤器占的字节数量
  uint32_t SizeInBytes() const {
	return table_->SizeInBytes();
  }

};
template<typename ItemType, uint32_t bitsPerItem, template<uint32_t> class TableType, typename HashFamily>
Status CuckooFilter<ItemType, bitsPerItem, TableType, HashFamily>::Add(const ItemType &item) {
  uint32_t i, tag;
  if (victim_.used) {
	return NotEnoughSpace;
  }

  GenerateIndexTagHash(item, i, tag);
  return AddImpl(i, tag);
}
template<typename ItemType, uint32_t bitsPerItem, template<uint32_t> class TableType, typename HashFamily>
Status CuckooFilter<ItemType, bitsPerItem, TableType, HashFamily>::AddImpl(const uint32_t i, const uint32_t tag) {
  uint32_t curIndex = i, curTag = tag, oldTag;

  for (uint32_t count = 0; count < kMaxCuckooCount; count++) {
	bool kickOut = count > 0;
	oldTag = 0;

	if (table_->InsertTagToBucket(curIndex, curTag, kickOut, oldTag)) {
	  numItems_++;
	  return OK;
	}

	if (kickOut) {
	  curTag = oldTag;
	}

	curIndex = AltIndex(curIndex, curTag);
  }

  victim_.index = curIndex;
  victim_.tag = curTag;
  victim_.used = true;

  return OK;
}
template<typename ItemType, uint32_t bitsPerItem, template<uint32_t> class TableType, typename HashFamily>
Status CuckooFilter<ItemType, bitsPerItem, TableType, HashFamily>::Contain(const ItemType &key) const {
  bool found = false;
  uint32_t i1, i2, tag;

  GenerateIndexTagHash(key, i1, tag);

  i2 = AltIndex(i1, tag);

  // 测试第二个 Bucket 的位置
  assert(i1 == AltIndex(i2, tag));

  found = victim_.used && (tag == victim_.tag) && (i1 == victim_.index || i2 == victim_.index);

  if (found || table_->FindTagInBuckets(i1, i2, tag)) {
	return OK;
  }
  return NotFound;
}
template<typename ItemType, uint32_t bitsPerItem, template<uint32_t> class TableType, typename HashFamily>
Status CuckooFilter<ItemType, bitsPerItem, TableType, HashFamily>::Delete(const ItemType &key) {
  uint32_t i1, i2, tag;

  GenerateIndexTagHash(key, &i1, &tag);
  i2 = AltIndex(i1, tag);

  if (table_->DeleteTagFromBucket(i1, tag)) {
	numItems_--;
	goto TryEliminateVictim;
  }else if(table_->DeleteTagFromBucket(i1, tag)){
	numItems_--;
	goto TryEliminateVictim;
  }else if(victim_.used&&tag==victim_.tag&&(i1==victim_.index||i2==victim_.index)){
	numItems_--;
	victim_.used=false;
  }else{
	return NotFound;
  }

  TryEliminateVictim:
  if(victim_.used){
	victim_.used=false;
	uint32_t i=victim_.index;
	uint32_t t=victim_.tag;

	AddImpl(i,t);
  }
  return OK;
}
template<typename ItemType, uint32_t bitsPerItem, template<uint32_t>class TableType, typename HashFamily>
std::string CuckooFilter<ItemType, bitsPerItem, TableType, HashFamily>::Info() const {
  std::stringstream ss;
  ss << "CuckooFilter Status:\n"
	 << "\t\t" << table_->Info() << "\n"
	 << "\t\tKeys stored: " << Size() << "\n"
	 << "\t\tLoad factor: " << LoadFactor() << "\n"
	 << "\t\tHashtable size: " << (table_->SizeInBytes() >> 10) << " KB\n";
  if (Size() > 0) {
	ss << "\t\tbit/key:   " << BitsPerItem() << "\n";
  } else {
	ss << "\t\tbit/key:   N/A\n";
  }
  return ss.str();
}


